// https://www.lintcode.com/problem/backpack-v/description

class Solution {
public:
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */

     int backPackV(vector<int> A, int m) {
        int n = A.size();
        if (n == 0) return 0;
        vector<vector<int>> res(n + 1, vector<bool>(m + 1, 0));
        res[0][0] = 0;
        for (int i = 1; i < n + 1; ++i) //前i个物品能拼出的方法数
        {
            for (int j = 0; j < m + 1; ++j)
            {
                res[i][j] = res[i - 1][j]; //第i个物品不放入
                if (j >= A[i - 1])
                {
                    res[i][j] = (res[i][j] + res[i - 1][j - A[i - 1]]);
                }
            }
        }
        return f[n][m];
    }

    // 空间优化，滚动数组->直接改成一维的，从右往左算，因为历史信息不会被再用了 （个：不可以重复放，所以前面更新过的也影响不到后面）
    // int backPackV(vector<int> &nums, int target) {
    //     vector<int> result(target + 1, 0);
    //     result[0] = 1;
    //     for (int i = 0; i < nums.size(); ++i)
    //     {
    //         for (int j = target; j >= nums[i]; --j)
    //         {
    //             result[j] += result[j - nums[i]];
    //         }
    //     }
    //     return result[target];
    // }
};